<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Perfect Cubes</title>
<meta name="description" content="Perfect Cubes">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00386_archivos/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">
 <h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">Perfect Cubes</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
For hundreds of years Fermat's Last Theorem, which stated simply that
for <i>n</i> &gt; 2 there exist no
integers <i>a</i>, <i>b</i>, <i>c</i> &gt; 1 such that  <img alt="tex2html_wrap_inline27" src="acm-00386_archivos/386img1.gif" align="middle" height="26" width="94">  , has remained
elusively unproven. (A recent proof is
believed to be correct, though it is still undergoing scrutiny.)
It is possible, however, to find integers
greater than 1 that satisfy the ``perfect cube'' equation
 <img alt="tex2html_wrap_inline29" src="acm-00386_archivos/386img2.gif" align="middle" height="30" width="127">  (e.g. a quick calculation
will show that the equation  <img alt="tex2html_wrap_inline31" src="acm-00386_archivos/386img3.gif" align="middle" height="30" width="145">  is indeed true).
This problem requires that you
write a program to find all sets of numbers {<i>a</i>, <i>b</i>, <i>c</i>, <i>d</i>} which
satisfy this equation for  <img alt="tex2html_wrap_inline35" src="acm-00386_archivos/386img4.gif" align="middle" height="25" width="57"> .
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Output</a></font></h2>
<p>
The output should be listed as shown below, one perfect cube per
line, in non-decreasing order of
<i>a</i> (i.e. the lines should be sorted by their a values). The values
of <i>b</i>, <i>c</i>, and <i>d</i> should also be listed
in non-decreasing order on the line itself. There do exist several
values of a which can be produced
from multiple distinct sets of <i>b</i>, <i>c</i>, and <i>d</i> triples. In these
cases, the triples with the smaller <i>b</i> values should be listed first.
</p><p>
</p><p>
The first part of the output is shown here:
</p><p>
</p><pre>Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)</pre>
<p>
</p><p>
</p><p>
<b>Note:</b> The programmer will need to be concerned with an efficient
implementation. The official
time limit for this problem is 2 minutes, and it is indeed possible to
write a solution to this problem
which executes in under 2 minutes on a 33 MHz 80386 machine.
Due to the distributed nature of
the contest in this region, judges have been instructed to make
the official time limit at their site
the greater of 2 minutes or twice the time taken by the judge's
solution on the machine being used to judge this problem.
</p><p>
</p></body></html>